/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2025-09-08
 * Time: 20:18
 */
public class TestCode4 {

    public static double largestSumOfAverages(int[] num, int k) {
        int n = num.length;
        double[][] dp = new double[n+1][k+1];
        double[] pre = new double[n+1];
        for(int i = 0; i < n; i++) {
            pre[i+1] = num[i] + pre[i];
        }
        // 初始化
        for(int i = 1; i <= n; i++) {
            dp[i][1] = pre[i] / i;
        }

        for(int j = 2; j <= k; j++) {
            for(int i = 1; i <= n; i++) {
                for(int x = j-1; x < i; x++) {
                    dp[i][j] = Math.max(dp[i][j],dp[x][j-1] + (pre[i]-pre[x]) / (i-x));
                }
            }
        }
        return dp[n][k];
    }
    public static void main(String[] args) {
        int[] num = {9,1,2,3,9};
        int k = 3;
        double ret = largestSumOfAverages(num,k);
        System.out.println(ret);
    }
}
